<!DOCTYPE html>
<html lang="en">
  <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta charset="UTF-8">
    <title>tgd's Code Jam Solver</title>
    <script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.2.16/angular.min.js"></script>



    <script>

"use strict";



function doChargingChaos(input) {
  console.log('Charging Chaos');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  function I64(num) {
    this.raw = '0000000000000000000000000000000000000000000000000000000000000000'.concat(num).substr(-64);
    this.xor = function(val) {
      var newVal = [];
      for (var i = 0; i < 64; ++i) {
        newVal.push(this.raw.charAt(i) ^ val.raw.charAt(i));
      }
      return parseInt(newVal.join(''), 2);
    }
  }
  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var N = lines[line].split(' ')[0];
    var L = lines[line++].split(' ')[1];
    var ief = lines[line++].split(' ');  //'I'nitial 'E'lectric 'F'low from the outlets
    var efr = lines[line++].split(' ');  //'E'lectric 'F'low 'R'equired by devices

    for (var j = 0; j < N; ++j) {
      ief[j] = new I64(ief[j]);  //parseInt(ief[j], 2);
      efr[j] = new I64(efr[j]);  //parseInt(efr[j], 2);
    }

    var matrix = [];

    for (var m = 0; m < N; ++m) {
      matrix.push([]);
      for (var n = 0; n < N; ++n) {
        matrix[m].push(ief[m].xor(efr[n]));  //ief[m] ^ efr[n]);
      }
    }

    var numSwitches = Infinity;

    for (var m = 0; m < N; ++m) {
      var temp = matrix[0][m];
      for (var n = 1; n < N; ++n) {
        var found = false;
        for (var o = 0; o < N; ++o) {
          if (matrix[n][o] === temp) {
            found = true;
            break;
          }
        }
        if (!found) {
          temp = -1;
          break;
        }
      }
      if (temp !== -1 && temp < numSwitches) {
        numSwitches = temp;
      }
    }

    solution += 'Case #' + i + ': ' + (numSwitches === Infinity ? 'NOT POSSIBLE' : (numSwitches === 0 ? numSwitches : numSwitches.toString(2).match(/(1)/g).length)) + '\n';
  }

  return solution;
}



function doChargingChaosNaive(input) {
  console.log('Charging Chaos');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var N = lines[line].split(' ')[0];
    var L = lines[line++].split(' ')[1];
    var ief = lines[line++].split(' ');  //'I'nitial 'E'lectric 'F'low from the outlets
    var efr = lines[line++].split(' ');  //'E'lectric 'F'low 'R'equired by devices

    for (var j = 0; j < N; ++j) {
      ief[j] = parseInt(ief[j], 2);
      efr[j] = parseInt(efr[j], 2);
    }

    efr.sort();
    var minSwitches = -1;
    for (var j = 0; j < Math.pow(2, L); ++j) {
      var temp = [];
      for (var k = 0; k < N; ++k) {
        temp.push(ief[k] ^ j);
      }
      temp.sort();
      var match = true;
      for (var k = 0; k < N; ++k) {
        if (efr[k] !== temp[k]) {
          match = false;
          break;
        }
      }
      if (match) {
        minSwitches = (j === 0 ? 0 : j.toString(2).match(/(1)/g).length);
        break;
      }
    }

    solution += 'Case #' + i + ': ' + (minSwitches === -1 ? 'NOT POSSIBLE' : minSwitches) + '\n';
  }

  return solution;
}



function doDeceitfulWar(input) {
  console.log('Deceitful War');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var N = lines[line++];
    var nBlocks = lines[line++].split(' ');
    var kBlocks = lines[line++].split(' ');

    for (var j = 0; j < N; ++j) {
      nBlocks[j] = parseFloat(nBlocks[j]);
      kBlocks[j] = parseFloat(kBlocks[j]);
    }
    
    nBlocks.sort();
    kBlocks.sort();
    var kBlocksTemp = [];

    var nWarPoints = 0;

    for (var m = 0; m < N; ++m) {
      var found = false;
      for (var n = 0; n < kBlocks.length; ++n) {
        if (kBlocks[n] > nBlocks[m]) {
          kBlocksTemp.push(kBlocks.splice(n, 1));
          found = true;
          break;
        }
      }
      if (!found) {
        ++nWarPoints;
        kBlocksTemp.push(kBlocks.splice(0, 1));
      }
    }

    kBlocks = kBlocksTemp.sort();
    var nDeceitfulWarPoints = 0;

    for (var m = 0; m < N; ++m) {
      var found = false;
      for (var n = kBlocks.length - 1; n >= 0; --n) {
        if (nBlocks[m] > kBlocks[n]) {
          kBlocks.splice(n, 1);
          found = true;
          ++nDeceitfulWarPoints;
          break;
        }
      }
      if (!found) {
        kBlocks.splice(kBlocks.length - 1, 1);
      }
    }

    solution += 'Case #' + i + ': ' + nDeceitfulWarPoints + ' ' + nWarPoints + '\n';
  }

  return solution;
}



function doMinesweeperMaster(input) {
  console.log('Minesweeper Master');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var T = lines[0];

  for (var i = 1; i <= T; ++i) {
    var params = lines[i].split(' ');
    var R = parseFloat(params[0]);
    var C = parseFloat(params[1]);
    var M = parseFloat(params[2]);

    console.log(T,R,C,M,i);

    solution += 'Case #' + i + ':\n'

    if ("has solution" === "has solution") {
      var cells = [];
      for (var r = 0; r < R; ++r) {
        cells.push([]);
        for (var c = 0; c < C; ++c) {
          cells[r].push('.');
        }
      }

      cells[r - 1][c - 1] = 'c';


      var remainingMines = M;
      var row = 0;
      var col = 0;

      //TODO: wrong, too much effort, not worth it
      while (remainingMines > 0) {
        cells[row][col] = '*';
        --remainingMines;
        ++col;
        if (col === C) {
          col = 0;
          ++row;
        }
      }

      for (var r = 0; r < R; ++r) {
        for (var c = 0; c < C; ++c) {
          solution += cells[r][c];
        }
        solution += '\n';
      }

    } else {
      solution += 'Impossible\n';
    }
  }

  return solution;
}



function doCookieClickerAlpha(input) {
  console.log('Cookie Clicker Alpha');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var T = lines[0];

  for (var i = 1; i <= T; ++i) {
    var params = lines[i].split(' ');
    var C = parseFloat(params[0]);
    var F = parseFloat(params[1]);
    var X = parseFloat(params[2]);

    var data = [];
    var sum = C / 2;
    var num = 0;
    
    //Insert initial row.
    data.push([sum, X / 2, sum, X / 2]);
 
    do {
      var rate = 2 + F * ++num;
      sum += C / rate;
      data.push([C / rate, X / rate, sum, data[data.length - 1][2] + X / rate]);
    } while(data[data.length - 1][3] < data[data.length - 2][3]);
    
    solution += 'Case #' + i + ': ' + data[data.length - 2][3] + '\n';
  }

  return solution;
}



function doMagicTrick(input) {
  console.log('Magic Trick');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var ans1 = lines[line++];
    var grid1 = [lines[line++].split(' '), lines[line++].split(' '), lines[line++].split(' '), lines[line++].split(' ')];
    var ans2 = lines[line++];
    var grid2 = [lines[line++].split(' '), lines[line++].split(' '), lines[line++].split(' '), lines[line++].split(' ')];
    var row1 = grid1[ans1 - 1];
    var row2 = grid2[ans2 - 1];

    var possibleCards = [];
    var result;

    for (var j = 0; j < 4; ++j) {
      for (var k = 0; k < 4; ++k) {
        if (row1[j] === row2[k]) {
          possibleCards.push(row1[j]);
        }
      }
    }
    
    if (possibleCards.length === 1) {
      result = possibleCards[0];
    } else if (possibleCards.length > 1) {
      result = 'Bad magician!';
    } else {
      result = 'Volunteer cheated!';
    }

    solution += 'Case #' + i + ': ' + result + '\n';
  }

  return solution;
}



function doStoreCredit(t) {
  console.log('Store Credit');
  var solution = '';
  var lines = t.split(/[\r\n]+/);
  
  var N = lines[0];
  
  for (var i = 1, x = 1; x <= N; ++x) {
    var C = parseInt(lines[i++]);
    var I = parseInt(lines[i++]);
    var prices = lines[i++].split(' ');
    
    for (var j = 0; j < prices.length - 1; ++j) {
      for (var k = j + 1; k < prices.length; ++k) {
        if (parseInt(prices[j]) + parseInt(prices[k]) === C) {
          solution += 'Case #' + x + ': ' + (j + 1) + ' ' + (k + 1) + '\n';
          
        }
      }
    }
  }

  return solution;
}



function doReverseWords(input) {
  console.log('Reverse Words');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var N = lines[0];

  for (var i = 1; i <= N; ++i) {
    var line = lines[i];
    line = line.split(' ').reverse().join(' ');
    solution += 'Case #' + i + ': ' + line + '\n';
  }

  return solution;
}



function doT9Spelling(input) {
  console.log('T9 Spelling');
  var solution = '';
  var lines = input.split(/[\r\n]+/);

  var N = lines[0];

  for (var i = 1; i <= N; ++i) {
    var desired_message = lines[i];
    var line = '', last_key = '', current_key = '';
    for (var j = 0, l = desired_message.charAt(j); j < desired_message.length; l = desired_message.charAt(++j)) {
      var seq = '';
      switch (l) {
        case 'c': seq += '2';
        case 'b': seq += '2';
        case 'a': seq += '2'; current_key = '2'; break;
        case 'f': seq += '3';
        case 'e': seq += '3';
        case 'd': seq += '3'; current_key = '3'; break;
        case 'i': seq += '4';
        case 'h': seq += '4';
        case 'g': seq += '4'; current_key = '4'; break;
        case 'l': seq += '5';
        case 'k': seq += '5';
        case 'j': seq += '5'; current_key = '5'; break;
        case 'o': seq += '6';
        case 'n': seq += '6';
        case 'm': seq += '6'; current_key = '6'; break;
        case 's': seq += '7';
        case 'r': seq += '7';
        case 'q': seq += '7';
        case 'p': seq += '7'; current_key = '7'; break;
        case 'v': seq += '8';
        case 'u': seq += '8';
        case 't': seq += '8'; current_key = '8'; break;
        case 'z': seq += '9';
        case 'y': seq += '9';
        case 'x': seq += '9';
        case 'w': seq += '9'; current_key = '9'; break;
        case ' ': seq += '0'; current_key = '0'; break;
      }
      if (last_key === current_key) {
        line += ' ';
      }
      line += seq;
      last_key = current_key;
    }

    solution += 'Case #' + i + ': ' + line + '\n';
  }

  return solution;
}



function doMinimumScalarProduct(input) {
  console.log('Minimum Scalar Product');
  var solution = '';
  var lines = input.split(/[\r\n]+/);
  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var n = lines[line++];
    var v1 = lines[line++].split(' ');
    var v2 = lines[line++].split(' ');

    v1.sort(function(a, b) { return a - b;});
    v2.sort(function(a, b) { return b - a;});

    var msp = 0;

    for (var j = 0; j < n; ++j) {
      msp += v1[j] * v2[j];
    }

    solution += 'Case #' + i + ': ' + msp + '\n';
  }

  return solution;
}



function doMilkshakes() {
}



function doBoilerPlateSolver(input) {
  console.log('Boiler Plate Solver');
  var solution = '';
  var lines = input.split(/[\r\n]+/);
  var T = lines[0];

  for (var i = 1,line = 1; i <= T; ++i) {
    var N = lines[line].split(' ')[0];
    var L = lines[line++].split(' ')[1];
    var ief = lines[line++].split(' ');
    var efr = lines[line++].split(' ');

    var someValue = 'foo';

    solution += 'Case #' + i + ': ' + someValue + '\n';
  }

  return solution;
}



angular.module('tgdCodeJam', [])
  .controller('CodeJamController', ['$scope', function($scope) {
    $scope.contests = [
      { title: 'Round 1A 2014', problems: [
        {id: 'A', title: 'Charging Chaos',        solver: doChargingChaos,         output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/2984486/dashboard#s=p0'},
        {id: 'B', title: 'Full Binary Tree',      solver: null,                    output: '', inputFilename: '', successful: false, url: 'https://code.google.com/codejam/contest/2984486/dashboard#s=p1'},
        {id: 'C', title: 'Proper Shuffle',        solver: null,                    output: '', inputFilename: '', successful: false, url: 'https://code.google.com/codejam/contest/2984486/dashboard#s=p2'},
      ]},
      { title: 'Qualification Round 2014', problems: [
        {id: 'A', title: 'Magic Trick',           solver: doMagicTrick,            output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/2974486/dashboard#s=p0'},
        {id: 'B', title: 'Cookie Clicker Alpha',  solver: doCookieClickerAlpha,    output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/2974486/dashboard#s=p1'},
        {id: 'C', title: 'Minesweeper Master',    solver: doMinesweeperMaster,     output: '', inputFilename: '', successful: false, url: 'https://code.google.com/codejam/contest/2974486/dashboard#s=p2'},
        {id: 'D', title: 'Deceitful War',         solver: doDeceitfulWar,          output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/2974486/dashboard#s=p3'},
      ]},
      { title: 'Qualification Round Africa 2010', problems: [
        {id: 'A', title: 'Store Credit',          solver: doStoreCredit,           output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/351101/dashboard#s=p0'},
        {id: 'B', title: 'Reverse Words',         solver: doReverseWords,          output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/351101/dashboard#s=p1'},
        {id: 'B', title: 'T9 Spelling',           solver: doT9Spelling,            output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/351101/dashboard#s=p2'},
      ]},
      { title: 'Round 1A 2008', problems: [
        {id: 'A', title: 'Minimum Scalar Product', solver: doMinimumScalarProduct, output: '', inputFilename: '', successful: true,  url: 'https://code.google.com/codejam/contest/32016/dashboard#s=p0'},
        {id: 'B', title: 'Milkshakes',             solver: doMilkshakes,           output: '', inputFilename: '', successful: false, url: 'https://code.google.com/codejam/contest/32016/dashboard#s=p1'},
      ]},
    ];
  }])
  .config(['$compileProvider', function($compileProvider) {
    $compileProvider.aHrefSanitizationWhitelist(/^data|https/);
  }])
  .directive('dropzone', function() {
    return {
      link: function(scope, element, attrs) {

        var getArticleElement = function (ele) {
          while (ele.nodeName !== 'ARTICLE') {
            ele = ele.parentNode;
          }
          return ele;
        }

        var dragenter = function(e) {
          var article = getArticleElement(e.target);

          article.dataset.inChild = e.target === article ? 'N' : 'Y';

          e.stopPropagation();
          e.preventDefault();

          angular.element(article).addClass('over');
        }

        var dragleave = function(e) {
          var article = getArticleElement(e.target);

          if (article === e.target && article.dataset.inChild === 'N') {
            angular.element(article).removeClass('over');
          }

          article.dataset.inChild = 'N';

          e.stopPropagation();
          e.preventDefault();
        }

        var dragover = function(e) {
          e.stopPropagation();
          e.preventDefault();
          return false;
        }

        var drop = function(e) {
          var article = getArticleElement(e.target);
          angular.element(article).removeClass('over');

          e.stopPropagation();
          e.preventDefault();

          var files = e.dataTransfer.files;
          handleFiles(files, scope.problem.solver);
        }

        var handleFiles = function(files, func) {
          var file = files[0];  //assume 1 file
          var reader = new FileReader();
          scope.problem.inputFilename = file.name;
          reader.onload = function(e) { scope.problem.output = encodeURIComponent(func(e.target.result)); scope.$apply(); };
          reader.readAsText(file);
        }

        element.on('dragenter', dragenter);
        element.on('dragleave', dragleave);
        element.on('dragover', dragover);
        element.on('drop', drop);
      }
    }
  });



function cancelDND(e) {  //put this on all the body events so accidental drops don't load files
  e.stopPropagation();
  e.preventDefault();
  return false;
}



    </script>

    <style>
      html,body {
        background: #fff;
        font-family: sans-serif;
        height: 100%;
        margin: 0;
        padding: 0;
        width: 100%;
        height:100%;
      }
      header,section,article{padding:.5em;}
      header {
        background: #000;
        box-shadow: 0 0 3px 3px #666;
        color: #fff;
      }
      section {
        background: #ccc;
        box-shadow: 0 0 3px 3px #999;
        color: #333;
        font-size: 1.5em;
        margin: 1em;
      }
      article {
        background: #eee;
        box-shadow: 0 0 3px 3px #aaa;
        margin: 0.5em;
      }
      article .id{color: #999;}
      article .title{color:#333;}
      article .success{color:#9c0;}
      article .failure{color:#f44;}
      article.over{
        background:#33B5E5;
        color:#fff;
        box-shadow:0 0 5px 5px #999;
      }
      article a{
        color:#09c;
        font-style:italic;
        font-weight:bold;
        text-decoration:none;
      }
      article a span{color:#999;font-weight:normal;font-size:.7em;}
      article a[download]{float:right;}
    </style>
  </head>
  <body data-ng-app="tgdCodeJam" data-ng-controller="CodeJamController" ondrop="cancelDND(event)" ondragenter="cancelDND(event)" ondragover="cancelDND(event)">
    <header>Drag and drop input files and then click "Output" to download results.  No error handling or commenting is being done, don't judge me.  Used Firefox mainly, should work in Chrome too.</header>
    <section data-ng-repeat="contest in contests">
      {{contest.title}}
      <article data-ng-repeat="problem in contest.problems" data-dropzone data-ng-hide="problem.solver == null">
        <a data-ng-href="{{problem.url}}">&#x1f517;</a>
        <span class="id">Problem {{problem.id}}.</span>
        <span class="title">{{problem.title}}</span>
        <span class="success" ng-show="problem.successful" title="Generates Correct Solutions">&#x1f44c</span>
        <span class="failure" ng-show="!problem.successful" title="Incomplete Solution.  Wrong.  Broken">&#x1f44e</span>
        <a download="{{problem.title}}.output.txt" title="{{problem.inputFilename}}" data-ng-href="data:text/plain;charset=utf-8,{{problem.output}}" data-ng-hide="problem.output == ''">
          Output 
          <span>({{problem.inputFilename}})</span>
        </a>
      </article>
    </section>
  </body>
</html>